COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input basic
C00008 00003
C00010 ENDMK
C⊗;
\input basic
\magnify{1300}
\ctrline{\bf  RANDOM DRIFT ON A LATTICE}
\par
\vskip 20pt
\ctrline{Joseph B.\ Keller}
\ctrline{Departments of Mathematics and Mechanical Engineering}
\ctrline{Stanford University, Stanford, CA   94305}
\vskip 30 pt
\noindent
{\it 1.  Formulation.}
\par
Let us consider a cloud of $k$ points, located at adjacent lattice sites on
 the $x$--{axis} at time $t$.  Let  $\nu(n,t)$ be the (random) number at 
 time $t$.  Let one of the $k$ points be chosen at random and suppose it is 
 at $j - 1$.  Then one of the leftmost points is moved to $j$ at time $t + 1$.
 Thus 
           
$$\nu(n,t+1)=\nu(n,t)+\delta↓{nj},\qquad \hbox{if}\; \nu(n-1,t)≠0,\eqno(1)$$
$$\nu(n,t+1)=\nu(n,t)-1,\qquad \hbox{if}\; \nu(n-1,t)=0.\eqno(2)$$
We shall denote by $N(n,t)$ the expectation of $\nu(n,t)$:
$$N(n,t)=E\nu(n,t).\eqno(3)$$
We now take the expectation of (1) and (2), replacing the conditions by their
 expectations:
$$N(n,t+1)=N(n,t)+k↑{-1}N(n-1,t),\qquad \hbox{if} \;N(n-1,t)≠0,\eqno(4)$$
$$N(n,t+1)=N(n,t)-1,\qquad \hbox{if} \;N(n-1,t)=0.\eqno(5)$$

\par
The model which we have just described mathematically arose in the analysis
of the simplex method of linear programming by ?????? and G.\ Dantzig.  By
 simulating this random process, they found that the cloud moves toward  
increasing $n$ with an average velocity $c(k)$ which seems to approach
$ek↑{-1}$ as $k$ becomes large.  P.\ Diaconis has found $c(k)$ analytically 
for $k=2,3,4,5$.  His results are
$$c(2)=1,\quad c(3)=2/3,\quad c(4)=2.04/4,\quad c(5)=2.1/5.$$
Our objective is to obtain $c(k)$ asymptotically for $k$ large, which we
shall do.  Our result confirms the value $ek↑{-1}$ suggested by the 
simulation, and is also in close agreement with Diaconis' results for
$k=3$, $4$ and $5$.
\par\penalty-1
\vskip 20 pt
\noindent
{\it 2.  Progressing wave solutions.}

We seek a progressing wave solution of (4) and (5) of the form 
$$N(n,t)=f(n-ct),\quad c>0.\eqno(6)$$
Here the waveform $f$ and the velocity $c$ are to be found.  We also require 
that 
$$f(x)=0,\quad \hbox{for} \;x≤-1.\eqno(7)$$
Now we use (6) and (7) in (4) and (5), and let $x=n-ct$ to obtain 
$$f(x-c)=f(x)+k↑{-1}f(x-1),\eqno(8)$$
$$f(-c)=f(0)-1.\eqno(9)$$

To solve (8) we try $f(x)=e↑{-\lambda{x}}$, and then (8) yields
$$e↑{-\lambda}(e↑{\lambda c}-1)=k↑{-1}.\eqno(10)$$
The left side of (10) increases from zero at $\lambda = 0$ to its maximum
$c(1-c)↑{c↑{-1}-1}$ at $\lambda=-c↑{1}log(1-c)$, and then decreases to zero 
as $\lambda$ tends to infinity.  The maximum increases with $c$ as $c$ increases 
from $c=0$ to $c=1$.  Thus there is a value $c↓m(k)$ at which the maximum of the 
left side of (10) is equal to $k↑{-1}$.  It is determined by the equation
$$c↓m(l-c↓m)↑{c↑{-1}↓m-1}=k↑{-1}.\eqno(11)$$

For $1>c>c↓m(k)$, (10) has two positive roots $\lambda↓1(c)$ and $\lambda↓2(c)$
which become equal at $c=c↓m(k)$.  There are no positive roots for  
$c<c↓m(k)$.  As $k$ becomes large the solution $c↓m(k)$ of (11) tends to
zero, and it is given asymptotically by
  
 

$$c↓m(k)~k{-1}e$$.
The solutions $c↓m(k)$ of (11) for ${k=3}$, 4 and 5 are compared in Table 1 
with Diaconis' exact results.

By linearly combining the two solutions $e{-\lambda↓1(c)x}$ and 
$e{-\lambda↓2(c)x}$ corresponding to a given $c>c↓m(k)$, we obtain a solution 
$f(x))$ of (8) containing two arbitrary constants.  They can be determined  
make $f$ satisfy (7) at $x=-1$ and $9$, and then $f(x)$ is given by

$$\eqalign{
f(x)⊗=[e↑{-\lambda↓l(c)(x+1)}-e↑{-\lambda↓2(c)(x+1)}]\cr
⊗\qquad\times [e↓{-\lambda↓1(c)}-e↑{-\lambda↓2(c)}-e↑{-\lambda↓1(c)(1-c)}
+e↑{-\lambda↓2(c)(1-c)}]↑{-1},\cr}$$ $$\qquad x≥1,\quad 1>c>c↓m(k),
=0,\quad x≤-1.(13)$$